P1637 三元上升子序列

题目描述

Erwin 最近对一种叫 thair 的东西巨感兴趣。。。

在含有 $n$ 个整数的序列 $a_1,a_2,\dots ,a_n$ 中，三个数被称作 thair 当且仅当 $i<j<k$ 且 $a_i<a_j<a_k$。

求一个序列中 thair 的个数。

输入格式

一个正整数 $n$,

$n$ 个整数 $a_1,a_2,\dots ,a_n$。

$1\le n\le 3\times {10}^4$，$1\le a_i\le {10}^5$。

输出格式

一行一个整数表示 thair 的个数。

Solution

逆序对/树状数组

由于这个题目 $a_i$ 的范围是 $[1,{10}^5]$，并不大，因此可以不进行离散化

对于下标为 $[2,n-1]$ 的每一个数，答案就是 $a_i$ 左边比 $a_i$ 小的数字个数乘以右边比 $a_i$ 大的数字个数。

#define lowbit(x) x&(-x)
int n, a[30010], l[30010], r[30010], tr1[100010], tr2[100010];
void add(int tr[], int x, int k) {
    while (x <= 1e5)tr[x] += k, x += lowbit(x);
}
int query(int tr[], int x) {
    int ans = 0;
    while (x)ans += tr[x], x -= lowbit(x);
    return ans;
}
void solve() {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    for (int i = 1;i <= n; i++) {
        add(tr1, a[i], 1);
        l[i] = query(tr1, a[i] - 1);
    }
    for (int i = n;i >= 1;i--) {
        add(tr2, a[i], 1);
        r[i] = n - i - query(tr2, a[i]) + 1;
    }
    ll ans = 0;
    for (int i = 2;i < n;i++)ans += l[i] * r[i];
    cout << ans << '\n';
}

若 $a_i$ 的数据较大，则可进行离散化，使得 $a_i$ 映射到的值始终不超过 $n$

离散化：

#define lowbit(x) x&(-x)
int n, l[30010], r[30010], tr1[100010], tr2[100010], a[30010], A[30010];
void add(int tr[], int x, int k) {
    while (x <= n)tr[x] += k, x += lowbit(x);
}
int query(int tr[], int x) {
    int ans = 0;
    while (x)ans += tr[x], x -= lowbit(x);
    return ans;
}
void solve() {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];A[i] = a[i];
    }
    //**离散化**
    sort(A + 1, A + 1 + n);
    for (int i = 1;i <= n;i++) {
        a[i] = lower_bound(A + 1, A + 1 + n, a[i]) - A;
    }
    for (int i = 1;i <= n; i++) {
        add(tr1, a[i], 1);
        l[i] = query(tr1, a[i] - 1);
    }
    for (int i = n;i >= 1;i--) {
        add(tr2, a[i], 1);
        r[i] = n - i - query(tr2, a[i]) + 1;
    }
    ll ans = 0;
    for (int i = 2;i < n;i++)ans += l[i] * r[i];
    cout << ans << '\n';
}